package com.leetcode;

import java.util.Random;

/**
 * 215. 数组中的第K个最大元素
 *
 * 升序
 */
public class Solution215_3 {

    private int[] nums;

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        return quickSelect(0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int left, int right, int k_small) {
        int idx = random_partition(left, right);
        if (idx == k_small) {
            return this.nums[idx];
        } else if (idx < k_small) {
            return quickSelect(idx + 1, right, k_small);
        } else {
            return quickSelect(left, idx - 1, k_small);
        }
    }

    private int random_partition(int left, int right) {
        Random random = new Random();
        int pivot = left + random.nextInt(right - left + 1);
        return partition(left, right, pivot);
    }

    private int partition(int left, int right, int pivot) {
        int part_num = this.nums[pivot];
        swap(pivot, right);
        int curIdx = left;
        for (int i = left; i <= right; i++) {
            if (this.nums[i] <= part_num) {
                swap(i, curIdx++);
            }
        }
        return curIdx - 1;
    }

    private void swap(int idx1, int idx2) {
        int tmp = this.nums[idx1];
        this.nums[idx1] = this.nums[idx2];
        this.nums[idx2] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1, 5, 6, 4};
//        int[] nums = new int[]{3};
        int k = 5;
        int num = new Solution215_3().findKthLargest(nums, k);
        System.out.println(num);
    }
}
